home *** CD-ROM | disk | FTP | other *** search
/ PC-Blue - MS DOS Public Domain Library / PC-Blue MS-DOS Public Domain Library - NYACC.iso / vol350 / prolog.arc / SAMPLES.ARC / MERGESRT.PRO < prev    next >
Encoding:
Text File  |  1987-05-19  |  1.3 KB  |  39 lines
  1. /* 
  2.    program for merge sort by John Sun: Runtime O(n log n) 
  3.  
  4.    mergesort(Unsorted_List, Sorted_List) :-
  5.        Sorted_List is a list of sorted integers in ascending order sorted
  6.        using merge sort of the Unsorted_List.
  7.  
  8.    To give this program a try use ?-mergesort([10,5,8,7,2,1,3,4,6,9], X).
  9.    Prolog should answer with:     X = [1,2,3,4,5,6,7,8,9,10]
  10.  
  11. */
  12.         mergesort([],     []).
  13.         mergesort([X],   [X]).
  14.         mergesort([X|Xs], Ys)      :- Xs \= [],
  15.                                       mergesort([X], Ls),
  16.                                       mergesort( Xs, Rs),
  17.                                       !,
  18.                                       merge(Ls, Rs, Ys).
  19.  
  20. /*
  21.    merge(Xs, Ys, Zs) :-
  22.        Zs is an ordered list of integers obtained from merging
  23.        the ordered lists of integers Xs and Ys.
  24.  
  25.    To give this merging predicate a try use ?-merge([1,3,5],[2,4,6],X).
  26.  
  27. */
  28.  
  29.         merge([X|Xs], [Y|Ys], [X|Zs])    :-
  30.             X < Y, !, merge(Xs, [Y|Ys], Zs).
  31.         merge([X|Xs], [Y|Ys], [X, Y|Zs]) :-
  32.             X = Y, !, merge(Xs, Ys, Zs).
  33.         merge([X|Xs], [Y|Ys], [Y|Zs])    :-
  34.             X > Y, !, merge([X|Xs], Ys, Zs).
  35.         merge(Xs, [], Xs)                :- !.
  36.         merge([], Ys, Ys)                :- !.
  37. 
  38.  
  39.